package Tree;

/**
 * 235、236.二叉树(二叉搜素树)的最近公共祖先
 * 给定一个二叉树(二叉搜素树), 找到该树中两个指定节点的最近公共祖先。
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 */
public class lowestCommonAncestor {
    /**
     * 二叉树
     * 一刷二刷解法一样不做记录
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (root == null) return null;
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        } else if (left == null && right == null) {
            return null;
        } else if (left != null && right == null) {
            return left;
        }
        return right;
    }

    /**
     * hot100一刷
     * hot100二刷
     */
    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null)
                return null;
            if (root == p || root == q) {
                return root;
            }
            TreeNode l = lowestCommonAncestor(root.left, p, q);
            TreeNode r = lowestCommonAncestor(root.right, p, q);
            if (l == null || r == null) {
                return l == null ? r : l;
            }
            return root;
        }
    }

    /**
     *  BST
     *  一刷二刷解法一样不做记录
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        //pq在右侧
        if (p.val > root.val && q.val > root.val) {
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if(right != null) return right;
        }
        //pq在左侧
        if(p.val < root.val && q.val < root.val) {
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            if(left != null) return left;
        }
        //pq在不同侧
        return root;
    }
}
